package leetcode.code1297;

import java.util.HashMap;
import java.util.Map;

import leetcode.IDebug;

public class Solution implements IDebug {

//	给你一个字符串 s ，请你返回满足以下条件且出现次数最大的 任意 子串的出现次数：
//
//	子串中不同字母的数目必须小于等于 maxLetters 。
//	子串的长度必须大于等于 minSize 且小于等于 maxSize 。

	public int maxFreq2(String s, int maxLetters, int minSize, int maxSize) {
		char[] cs = s.toCharArray();
		Map<String, Integer> cnts = new HashMap<>();
		int ans = 0;
		for (int size = minSize; size <= maxSize; size++) {
			int kinds = 0;
			int[] hash = new int[26];
			for (int i = 0; i < cs.length; i++) {
				int in = cs[i] - 'a';
				if (hash[in]++ == 0) {
					kinds++;
				}
				int l = i - size + 1;
				if (l >= 0) {
					if (kinds <= maxLetters) {
						String cur = new String(cs, l, size);
						int cnt = cnts.getOrDefault(cur, 0) + 1;
						cnts.put(cur, cnt);
						ans = Math.max(cnt, ans);
					}
					int out = cs[l] - 'a';
					if (--hash[out] == 0) {
						kinds--;
					}
				}
			}
		}
		return ans;
	}

	public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
		char[] cs = s.toCharArray();
		Map<String, Integer> cnts = new HashMap<>();
		int ans = 0;
		int size = minSize;
		int kinds = 0;
		int[] hash = new int[26];
		for (int i = 0; i < cs.length; i++) {
			int in = cs[i] - 'a';
			if (hash[in]++ == 0) {
				kinds++;
			}
			int l = i - size + 1;
			if (l >= 0) {
				if (kinds <= maxLetters) {
					String cur = new String(cs, l, size);
					int cnt = cnts.getOrDefault(cur, 0) + 1;
					cnts.put(cur, cnt);
					ans = Math.max(cnt, ans);
				}
				int out = cs[l] - 'a';
				if (--hash[out] == 0) {
					kinds--;
				}
			}
		}
		return ans;
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
